package m202405.d13;

import java.util.ArrayList;
import java.util.List;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/5/13 17:22
 */
public class Q200 {

    public static void main(String[] args) {
        Q200 q200 = new Q200();
        int i = q200.numIslands(new char[][]{
                {'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '0', '0'},
        });
        System.out.println();
    }

    public int numIslands(char[][] grid) {
        List<Island> list = new ArrayList<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == '0') {
                    continue;
                }
                Position position = new Position(j, i);
                List<Island> index = new ArrayList<>();
                for (Island island : list) {
                    if (island.contains(position)) {
                        index.add(island);
                    }
                }
                if (index.isEmpty()) {
                    list.add(new Island(position));
                } else {
                    List<Position> positions = new ArrayList<>();
                    positions.add(position);
                    for (Island island : index) {
                        list.remove(island);
                        positions.addAll(island.positions);
                    }
                    list.add(new Island(positions));
                }
            }
        }
        return list.size();
    }

    private static class Island {
        List<Position> positions;

        public Island(List<Position> positions) {
            this.positions = positions;
        }

        public Island(Position position) {
            positions = new ArrayList<>();
            positions.add(position);
        }

        private boolean contains(Position position) {
            for (Position p : positions) {
                if (p.nei(position)) {
                    return true;
                }
            }
            return false;
        }
    }

    private static class Position {
        int x;
        int y;

        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }

        private boolean nei(Position position) {
            if (position.x == this.x) {
                return position.y == this.y - 1 || position.y == this.y + 1;
            }
            if (position.y == this.y) {
                return position.x == this.x - 1 || position.x == this.x + 1;
            }
            return false;
        }
    }
}
